{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make the Prefix Sum Non-negative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makePrefSumNonNegative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使前缀和数组非负"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>下标从0开始</strong> 的整数数组 <code>nums</code> 。你可以任意多次执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从 <code>nums</code> 中选择任意一个元素，并将其放到 <code>nums</code> 的末尾。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>nums</code> 的前缀和数组是一个与 <code>nums</code> 长度相同的数组 <code>prefix</code> ，其中 <code>prefix[i]</code> 是所有整数 <code>nums[j]</code>（其中 <code>j</code> 在包括区间 <code>[0，i]</code> 内）的总和。</p>\n",
    "\n",
    "<p>返回使前缀和数组不包含负整数的最小操作次数。测试用例的生成方式保证始终可以使前缀和数组非负。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,-5,4]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>我们不需要执行任何操作。\n",
    "给定数组为 [2, 3, -5, 4]，它的前缀和数组是 [2, 5, 0, 4]。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,-5,-2,6]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以对索引为1的元素执行一次操作。\n",
    "操作后的数组为 [3, -2, 6, -5]，它的前缀和数组是 [3, 1, 7, 2]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-the-prefix-sum-non-negative](https://leetcode.cn/problems/make-the-prefix-sum-non-negative/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-the-prefix-sum-non-negative](https://leetcode.cn/problems/make-the-prefix-sum-non-negative/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,-5,4]', '[3,-5,-2,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        \n",
    "        # 初始化一个最小堆\n",
    "        heap = []\n",
    "        \n",
    "        # pre 用于保存前缀和\n",
    "        pre = 0\n",
    "        \n",
    "        # ans 记录操作次数\n",
    "        ans = 0\n",
    "        \n",
    "        # 遍历数组\n",
    "        for num in nums:\n",
    "            \n",
    "            # 累加前缀和\n",
    "            pre += num\n",
    "            \n",
    "            # 将当前数字加入最小堆\n",
    "            heapq.heappush(heap, num)\n",
    "            \n",
    "            # 当前缀和小于 0 时\n",
    "            if pre < 0:\n",
    "                \n",
    "                # 从前缀和中减去当前前缀的最小数字\n",
    "                pre -= heapq.heappop(heap)\n",
    "                \n",
    "                # 操作次数加一\n",
    "                ans += 1\n",
    "        \n",
    "        # 返回总的操作次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "\n",
    "        # if sum(nums)<0: return -1  #加上这一行，就可以通过LCP30了\n",
    "        heap = []\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            pre+=num\n",
    "            heapq.heappush(heap,num) #因为不能排除需要移走的就是当前值，所以先push如果出问题了再pop\n",
    "            if pre<0: \n",
    "                pre-=heapq.heappop(heap)\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "\n",
    "        # if sum(nums)<0: return -1  #加上这一行，就可以通过LCP30了\n",
    "        heap = []\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            pre+=num\n",
    "            heapq.heappush(heap,num) #因为不能排除需要移走的就是当前值，所以先push如果出问题了再pop\n",
    "            if pre<0: \n",
    "                pre-=heapq.heappop(heap)\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        # 同 LCP.30\n",
    "        heap = []\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            heappush(heap, num)\n",
    "            if pre < 0:\n",
    "                pre -= heappop(heap)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        h = []\n",
    "        ans = s = 0\n",
    "        for v in nums:\n",
    "            s += v\n",
    "            if v < 0: heappush(h, v)\n",
    "            while s < 0:\n",
    "                s -= heappop(h)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        heap, res, sm = [], 0, 0\n",
    "        for i in nums:\n",
    "            sm += i\n",
    "            if i < 0: heapq.heappush(heap, i)\n",
    "            if sm < 0:\n",
    "                sm -= heapq.heappop(heap)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0:\n",
    "                heapq.heappush(pq, nums[i])\n",
    "            s += nums[i]\n",
    "            if s < 0:\n",
    "                smallest = heapq.heappop(pq)\n",
    "                s -= smallest\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        h = []\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            if s < 0:                           \n",
    "                if h and x > h[0]:\n",
    "                    s -= heappop(h)                    \n",
    "                    ans += 1\n",
    "                else:\n",
    "                    s -= x\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if x < 0:\n",
    "                    heappush(h, x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        h = []\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            if s < 0:                           \n",
    "                if h and x > h[0]:\n",
    "                    s -= heappop(h)                    \n",
    "                    ans += 1\n",
    "                else:\n",
    "                    s -= x\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if x < 0:\n",
    "                    heappush(h, x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePrefSumNonNegative(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        h = []\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            if s < 0:                           \n",
    "                if h and x > h[0]:\n",
    "                    s -= heappop(h)  \n",
    "                    heappush(h, x)                  \n",
    "                    ans += 1\n",
    "                else:\n",
    "                    s -= x\n",
    "                    \n",
    "                    ans += 1\n",
    "            else:\n",
    "                if x < 0:\n",
    "                    heappush(h, x)\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
